/**
 * https://leetcode.cn/problems/frog-position-after-t-seconds/submissions/582755499/
 * 1377.T 秒后青蛙的位置 1824
 * difficulty 陈贝纯 2024.11.24
 * dfs
 */


class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        double gl=1;
        vector<vector<int>> adj(n+1);
        for(auto edge:edges){
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        vector<bool> v(n+1,true);
        vector<int> parent(n+1,0);
        vector<int> d(n+1,0);
        queue<int> q;
        q.push(1);
        v[1]=false;
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            for(auto num:adj[cur]){
                if(v[num]){
                    v[num]=false;
                    parent[num]=cur;
                    q.push(num);
                    d[cur]++;
                }
            }
        }
        int h=target;
        while(h!=1&&t--){
            gl/=d[parent[h]];
            h=parent[h];
        }
        if(h!=1||t!=0&&d[target]!=0){
            return 0;
        }
        return gl;
    }
};
